package com.cjm.algorithm.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Ti240423015 {
    public List<List<Integer>> threeSum(int[] nums) {
        // 新建一个集合
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        // 如果数量都小于3，那么也就不用算了
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }
        // 对这些元素进行排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            // 已经前面已经排过序了， 所以当这里大于0的时候，后面的元素更大， 还搞个毛线
            if (nums[i] > 0) {
                // 直接结束了， 还继续个毛线， 大家都是抄的， 没有看过吗？
                return result;
            }
            // 如果遍历到的元素与前面的元素一样， 那么跳过
            if (i > 0 && nums[i] == nums[i - 1]) {
                // 因为这里是不重复的三元组， 所以重复的话需要删除掉， 也就是不要这个元素
                continue;
            }

            // 左端， 右端
            int l = i + 1, r = nums.length - 1;
            // 当左小于右时
            while (l < r) {
                // 来请个和
                int sum = nums[i] + nums[l] + nums[r];
                // 如果已经是目标和了
                if (sum == 0) {
                    // 将这几个值给加入到集合中去
                    result.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    // 来， 我们接着移动元素， 去找其它可能的元素
                    // 左侧元素必须小于右侧的元素， 同上面一样， 因为是不重复的三元组
                    while (l < r && nums[l] == nums[l + 1]) {
                        // 左侧走起
                        l++;
                    }
                    // 左侧元素必须小于右侧的元素， 同上面一样， 因为是不重复的三元组
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    // 上面的两个while只是去重了， 现在才需要再走各一步
                    l++;
                    r--;
                } else if (sum < 0) {
                    // 如果小的话， 那么证明这个和小了， 那需要左侧的元素右移
                    l++;
                } else {
                    // 如果大的话， 那么证明这个和大了， 那需要右侧的元素左移
                    r--;
                }
            }
        }
        return result;
    }
}
